OPINION

BERZON, Circuit Judge:

A magistrate judge denied petitioner Keith Andrew Mitchell's motion to stay and abey his 28 U.S.C. § 2254 habeas corpus petition while he exhausted some of his claims in state court. We hold that, in the context of a section 2254 habeas petition, this type of motion is generally (but not always) dispositive as to the unexhausted claims. When it is dispositive, a magistrate judge is without authority to "hear and determine" such a motion, but rather must submit a report and recommendation to the district court. 28 U.S.C. § 636(b)(1)(A)-(B).

I.

Keith Andrew Mitchell was convicted of first degree murder at a jury trial in California state court. He was sentenced to fifty years to life in prison. On direct appeal, Mitchell, represented by counsel, raised several claims challenging the trial court's jury instructions. The California Court of Appeal and California Supreme Court denied relief.

Proceeding pro se, Mitchell then filed his first federal habeas petition. The state moved to dismiss the petition for failure to exhaust some of the claims, and Mitchell voluntarily dismissed the petition without prejudice so he could exhaust his state remedies.

Still within the statute of limitations, 28 U.S.C. § 2244(d)(1), and proceeding pro se, Mitchell then filed a second federal habeas petition, at issue in this case, asserting five due process claims. Three of the claims corresponded to the arguments he had presented to the California courts on direct appeal. The other two claims, both relating to a gang sentencing enhancement, had been asserted in the first federal petition. The new petition was referred to a magistrate judge, authorized by the district court "to consider preliminary matters and conduct all further hearings as may be appropriate or necessary," and thereafter to issue a report and recommendation to the judge.

The state once again moved to dismiss the petition, arguing that the two gang claims were not exhausted. As a result, the state argued, the petition was "mixed," and the only proper resolutions were either to strike the unexhausted claims or to dismiss the entire petition.

Mitchell responded by filing a motion to stay the case to allow him to exhaust the two claims, citing Rhines v. Weber, 544 U.S. 269, 125 S.Ct. 1528, 161 L.Ed.2d 440 (2005). He represented that he had already filed state habeas petitions regarding the two claims, and that he had reasonably relied on his appointed attorney in the state proceedings to raise all of his potential claims on direct appeal. The state opposed the motion, arguing that there was no evidence Mitchell actually had filed any state habeas petition.

The magistrate judge issued an order addressing both the motion to dismiss and the motion to stay. Although Mitchell had not filed an opposition to the motion to dismiss, the magistrate judge concluded that Mitchell's motion to stay "impliedly concede[d] that at least one of his claims is unexhausted." The magistrate judge also reviewed the record and concluded that the two gang claims had not been raised in the state direct appeals and that Mitchell had offered no proof that the alleged state habeas petitions had been filed. As a result, the magistrate judge concluded, the motion to dismiss was "well taken."

As for the motion to stay, the magistrate judge noted that Rhines requires a showing of good cause for the failure to exhaust claims in state court. He found that a stay would be "inappropriate" in this case, as Mitchell had dismissed his prior petition "specifically to exhaust his state remedies with respect to the two unexhausted claims" also asserted in the current petition, yet "took no action to exhaust those claims."

The magistrate judge then returned to the motion to dismiss, noting that, as a mixed petition not eligible for a stay under Rhines, the petition was "subject to dismissal." The magistrate judge granted Mitchell leave to amend his petition to remove the unexhausted claims and indicated that, if Mitchell declined to do so, the magistrate judge would "issue a recommendation that the Petition be dismissed without prejudice for failure to exhaust."

Mitchell did move to remove "all unexhausted claims" from his petition. The magistrate judge granted Mitchell's motion and denied the motion to dismiss as moot.

Subsequently, the magistrate judge issued a report and recommendation to the district judge regarding the pared-down petition. In discussing the case's procedural history, the magistrate judge noted that he had previously denied Mitchell's stay motion for lack of good cause, had granted Mitchell's motion to dismiss his unexhausted claims, and had denied the state's motion to dismiss as moot. On the merits of the remaining three claims, the magistrate judge recommended that the court deny relief. Mitchell objected, also on the merits of the three exhausted claims.

After de novo review, the district court adopted the report and recommendation and dismissed the petition with prejudice. The district court did not address the denial of the stay motion at all. Mitchell timely appealed.

We granted a certificate of appealability, see 28 U.S.C. § 2253(c), as to "whether the magistrate judge exceeded his authority by issuing, without the parties' consent, orders denying appellant's motion for a stay and abeyance, dismissing two of appellant's claims, and denying as moot appellee's motion to dismiss."

II.

The authority of magistrate judges "is a question of law subject to de novo review." United States v. Carr, 18 F.3d 738, 740 (9th Cir.1994).

"The power of federal magistrate judges is limited by 28 U.S.C. § 636." Estate of Conners by Meredith v. O'Connor, 6 F.3d 656, 658 (9th Cir.1993) (citing Reynaga v. Cammisa, 971 F.2d 414, 416 (9th Cir.1992)); see also Flam v. Flam, 788 F.3d 1043, 1046, No. 12-17285, 2015 WL 3540771 at *2 (9th Cir. June 8, 2015). Pursuant to section 636, magistrate judges may hear and determine nondispositive matters, but not dispositive matters, in § 2254 proceedings. Hunt v. Pliler, 384 F.3d 1118, 1123 (9th Cir.2004). Dispositive matters are those listed in section 636(b)(1)(A), as well as "analogous" matters. See Flam, 788 F.3d at 1046, 2015 WL 3540771 at *2; United States v. Rivera-Guerrero, 377 F.3d 1064, 1067 (9th Cir.2004); accord PowerShare, Inc. v. Syntel, Inc., 597 F.3d 10, 13 (1st Cir.2010); Vogel v. U.S. Office Prods. Co., 258 F.3d 509, 515 (6th Cir.2001).1 "To determine whether a motion is dispositive, we have adopted a functional approach that looks to the effect of the motion, in order to determine whether it is properly characterized as dispositive or non-dispositive of a claim or defense of a party." Flam, 788 F.3d at 1046, 2015 WL 3540771 at *2 (internal quotation marks and alteration omitted). As to any dispositive matter, the magistrate judge is authorized, absent consent, only to issue a report and recommendation to the district judge, who in turn must undertake de novo review.2

Mitchell argues that the magistrate judge overstepped his authority by denying the motion to stay and abey his petition pending exhaustion.3 We agree.

"[W]here the denial of a motion to stay is effectively a denial of the ultimate relief sought, such a motion is considered dispositive, and a magistrate judge lacks the authority to `determine' the matter." S.E.C. v. CMKM Diamonds, Inc., 729 F.3d 1248, 1260 (9th Cir.2013) (citing Reynaga, 971 F.2d at 416-17). By contrast, a motion to stay is nondispositive where it "[does] not dispose of any claims or defenses and [does] not effectively deny ... any ultimate relief sought." Id.

CMKM Diamonds fell into the latter, nondispositive category. In that case, a Securities and Exchange Commission civil enforcement action, one of the defendants moved to stay the civil proceedings until a related criminal case had concluded. Id. at 1251, 1254. A magistrate judge denied the motion, and we held the magistrate judge within his authority in doing so. Id. at 1260. The defendant had "simply speculated that he might have stronger evidence to support his position in the civil proceedings if he was able to go through the criminal proceedings first." Id. Such speculation, we held, was insufficient to establish that the denial of a stay would either "dispose of any claims or defenses" or "effectively deny him any ultimate relief sought." Id. The magistrate judge was therefore empowered to hear and determine the matter. Id.

In so holding, CMKM Diamonds cited the rule established by our prior decision in Reynaga. The prisoner plaintiff in Reynaga filed a pro se lawsuit under 42 U.S.C. § 1983, alleging that the judge, district attorneys, and public defender involved in his state criminal case had denied him a fair trial. 971 F.2d at 415. The case was referred to a magistrate judge, who determined that the defendants were immune from money damages and that the injunction sought — namely early release from prison — could only be pursued through habeas corpus. Id. The magistrate judge thus ordered the action stayed until the plaintiff exhausted his state remedies and directed the clerk of court to administratively close the file. Id.

We concluded on appeal that it was "clear" that, absent consent, the magistrate judge's stay order "was beyond his authority." Id. at 416. Among other things, we said in support of our conclusion, "[t]he Magistrate's imposition of the stay effectively denied Reynaga's request for an injunction," and "the Magistrate's order was in essence an involuntary dismissal of Reynaga's action." Id. at 416-17. Both a motion for injunctive relief and a motion for involuntary dismissal are among the specifically enumerated dispositive matters listed in section 636(b)(1)(A). Id.

Taking CMKM Diamonds and Reynaga together, the dispositive question for us is whether the motion to stay and abey at issue here was effectively dispositive of a claim or defense or of the ultimate relief sought. See Flam, 788 F.3d at 1046, 2015 WL 3540771 at *2. As Rhines v. Weber, 544 U.S. 269, 125 S.Ct. 1528, 161 L.Ed.2d 440 (2005), makes clear, the answer is "yes." Indeed, at oral argument the state conceded that the stay denial in this case "was tantamount to a dismissal" of the unexhausted claims, and there was "no way" Mitchell would be able to return to federal court to assert those claims later.

Under Rhines, a section 2254 habeas petitioner may seek to stay and abey his petition while he exhausts his claims in state court. This procedure addresses the difficulties posed by the interaction of Rose v. Lundy, 455 U.S. 509, 102 S.Ct. 1198, 71 L.Ed.2d 379 (1982), and the Antiterrorism and Effective Death Penalty Act of 1996 (AEDPA).

Lundy held that district courts were required to dismiss without prejudice "mixed" section 2254 habeas petitions — that is, those including both exhausted and unexhausted claims. 455 U.S. at 510, 102 S.Ct. 1198. As Rhines explained, Lundy held this "requirement of `total exhaustion'" before a petition may proceed was required by "the interests of comity and federalism." Rhines, 544 U.S. at 273-74, 125 S.Ct. 1528. Fourteen years later, Congress enacted AEDPA, which imposed a one-year statute of limitations for the filing of a federal habeas petition. While that limitations period is tolled "during the pendency of a `properly filed application for State post-conviction or other collateral review,' [28 U.S.C.] § 2244(d)(2), the filing of a petition for habeas corpus in federal court does not toll the statute of limitations." Id. at 274-75, 125 S.Ct. 1528.

Considering the implications of the enactment of AEDPA for the continued viability of the Lundy rule requiring dismissal of all mixed petitions, Rhines began from the recognition that "[i]f a petitioner files a timely but mixed petition in federal district court, and the district court dismisses it under Lundy after the limitations period has expired, this will likely mean the termination of any federal review." Id. at 275, 125 S.Ct. 1528. Rhines therefore authorized a "stay-and-abeyance' procedure," under which the district court, "rather than dismiss the mixed petition," may "stay the petition and hold it in abeyance while the petitioner returns to state court to exhaust his previously unexhausted claims." Id. Concerned that "[s]tay and abeyance, if employed too frequently, has the potential to undermine" AEDPA's purposes of reducing delay and requiring petitioners to exhaust state remedies before coming to federal court, Rhines instructed that "the district court should stay, rather than dismiss, the mixed petition," only "in limited circumstances," namely when three conditions are met: "[(1)] the petitioner had good cause for his failure to exhaust, [(2)] his unexhausted claims are potentially meritorious, and [(3)] there is no indication that the petitioner engaged in intentionally dilatory litigation tactics." Id. at 277-78, 125 S.Ct. 1528.4

In light of Rhines, we conclude that a motion to stay and abey section 2254 proceedings is generally (but not always) dispositive of the unexhausted claims. Rhines acknowledged "the gravity of th[e] problem" of the interaction of Lundy's total exhaustion rule with AEDPA's one-year statute of limitation, "and the difficulty it has posed for petitioners." Rhines, 544 U.S. at 275, 125 S.Ct. 1528. "[P]etitioners who come to federal court with `mixed' petitions run the risk of forever losing their opportunity for any federal review of their unexhausted claims," id., because, absent a stay, they are presented with two choices, each of which will ordinarily result in precluding some or all of their claims: Either they may voluntary dismiss unexhausted claims, proceeding on only the exhausted ones, or they may decline to do so, leading to dismissal of the entire petition. Either kind of dismissal would be, in form, without prejudice. But, because the one-year statute of limitations is not tolled while the federal petition is pending, Duncan v. Walker, 533 U.S. 167, 181, 121 S.Ct. 2120, 150 L.Ed.2d 251 (2001), and because state proceedings can be lengthy and unpredictable, in most cases either option will mean that a petitioner will be barred from federal review of some or all of his claims by the time he exhausts them. If a petitioner voluntarily dismisses his unexhausted claims, it is very likely that final state court exhaustion of unexhausted claims will come too late to allow the claims to be heard in federal court, whether because (1) the statute of limitations period will have run on the claims and they will not relate back to the filing of the petition because they do not "arise[] from the same core of operative facts as a claim contained in the original petition," Ford v. Gonzalez, 683 F.3d 1230, 1237 n. 3 (9th Cir.2012) (internal quotation marks omitted); (2) the remaining federal habeas petition will have been decided by the time the state courts act on the new habeas claims, triggering the onerous requirements for filing a second or successive habeas petition, 28 U.S.C. § 2244(b); or (3) both. Similarly, if a petitioner chooses to accept dismissal of the entire petition under Lundy, he will very likely be barred from reasserting any of his claims in federal court by AEDPA's statute of limitations. In either event, the result is the same as to the unexhausted claims: The petitioner will lose the opportunity ever to present those claims to a federal habeas court.5 Thus, in this case, like Reynaga and unlike CMKM Diamonds, the magistrate judge's order was effectively dispositive of the unexhausted claims and, therefore, beyond his authority.

Indeed, we have previously recognized, in similar but not identical circumstances, that the interaction of AEDPA's statute of limitations and Lundy's total-exhaustion rule constrains the authority of magistrate judges. Hunt v. Pliler considered a magistrate judge's order holding a habeas petition mixed and warning that, unless the petitioner sought leave to file an amended petition without the unexhausted claims, the court would dismiss the petition in full under Lundy. 384 F.3d at 1120. The petitioner refused to do so and, after a "tortuous procedural hegira," the district court ultimately dismissed the petition with prejudice. Id. at 1120-23. We vacated the court's judgment, citing, in part, the court's and the magistrate judge's "fail[ure] to comply with § 636 and Rule 72, depriving Hunt of the right to de novo review by the district court of the magistrate judge's pivotal determination that the [petition] contained unexhausted claims." Id. at 1125. That determination was pivotal, we explained, because it "required Hunt to forfeit the claims [the magistrate judge] found unexhausted or face dismissal of the entire petition, effectively with prejudice because any newly filed petition would be barred by AEDPA's one-year statute of limitations." Id. at 1124 (citing 28 U.S.C. § 2244(d)); see also id. (observing that the magistrate judge's order could "hardly be considered equivalent to a dismissal with leave to amend because [it] compelled Hunt to abandon claims he contended had been exhausted or face dismissal of his entire petition with prejudice"). We therefore held that the magistrate judge's determination, purportedly on his own authority, that the petition was mixed "exceeded his statutory authority." Id.

Hunt is different from this case in that the petitioner in Hunt did not seek a stay pending exhaustion in state court, id. at 1125, and Mitchell did not affirmatively contest that his petition was mixed. But Hunt held that the magistrate judge could not hear and determine the question whether the petition was mixed because the resolution of that issue would have dispositive effect as to the unexhausted claims: If the petition was mixed, Hunt recognized, the choices confronting the petitioner would be to either "abandon" his purportedly unexhausted claims or else face "dismissal of the entire petition, effectively with prejudice," because of AEDPA's statute of limitations. Id. at 1124. The stay-and-abey motion at issue here was, as explained above, dispositive for the same reason. In the shadow of Lundy and AEDPA, the denial of a Rhines stay, like a determination that the petition is mixed, generally amounts to dismissal of the unexhausted claims with prejudice.

Finally, Flam recently held that a motion to remand a removed case to state court is a dispositive matter under our "functional approach." Flam, 788 F.3d at 1046-47, 2015 WL 3540771 at *2-3. Flam agreed with several other circuits that "such a remand order is `dispositive insofar as proceedings in the federal court are concerned,'" because "such an order `preclusively determines the important point that there will not be a federal forum available to entertain a particular dispute.'" Id. at 1047, 2015 WL 3540771 at *3 (quoting In re U.S. Healthcare, 159 F.3d 142, 146 (3d Cir.1998)). Because remand orders "put litigants out of federal court," Flam held, they are dispositive in the relevant sense. Id.

Much the same is true in this context. The denial of a motion to stay and abey is "dispositive insofar as proceedings in the federal court are concerned," because "such an order preclusively determines the important point that there will not be a federal forum available to entertain" the petitioner's unexhausted claims. Id. (internal quotation marks omitted).

In sum, the magistrate judge in this case had no authority to hear and determine the motion to stay and abey habeas proceedings to permit exhaustion of claims. He was, instead, required to submit a report and recommendation to the district court on that matter, for de novo review.

Because, "the procedure leading to [the] dismissal" of this habeas petition "failed to comply with § 636," Hunt, 384 F.3d at 1125, we vacate the district court's judgment and remand for further proceedings, guided by the principle that "we cannot countenance a magistrate judge's unauthorized" orders, Allen v. Meyer, 755 F.3d 866, 869 (9th Cir.2014), nor the results flowing from such orders, cf. Hunt, 384 F.3d at 1125.

The magistrate judge should have issued a report and recommendation as to the motion to stay and abey. The district court should therefore undertake, on remand, de novo review as to whether such a stay was warranted at the time of the magistrate judge's order. The district court may consider the magistrate judge's order on the stay as a report and recommendation, in which case the court should afford the parties an opportunity to lodge objections. See Rivera-Guerrero, 377 F.3d at 1071 (remanding "for the district court to apply de novo review ... treat[ing] the magistrate judge's `order' as proposed findings and recommendations"). If the district court concludes that no stay was warranted, then the magistrate judge's unauthorized action was harmless, and the district court may reimpose its previous order. See id.

If a stay was warranted, then the district court must determine what prejudice the petitioner suffered as a result. The pertinent question is: Would the case have progressed differently had a stay been granted, and, if so, how?

The magistrate judge's unauthorized denial of the motion to stay and abey proceedings led directly to Mitchell's voluntary dismissal of two of his claims. The magistrate judge expressly linked the two issues in his order, noting that, because the petition was not eligible for a Rhines stay, unless Mitchell voluntarily dismissed his unexhausted claims, the magistrate judge would recommend that the state's motion to dismiss be granted. Mitchell did so shortly thereafter. But for the magistrate judge's unauthorized action, if a stay was warranted, the case would have been stayed while Mitchell sought to exhaust the two unexhausted claims. Thus, if a stay should have been granted, the unauthorized stay denial caused Mitchell to lose the opportunity for a merits review on habeas of those two claims. Consequently, if the district court determines that a stay was warranted at the time, it should either stay the case under Rhines, if those claims remain unexhausted, or, if now exhausted, proceed to consider those claims as if they had never been dismissed.6

We vacate the judgment of the district court and remand for proceedings consistent with this opinion.7

VACATED AND REMANDED.